package ljl.alg.wangzheng_camp.round1.bisection;

/*
 * 这次是找旋转数组最小值了
 * */
public class _153_find_min {
    
    /**
     * 蒙对了。。。
     * 但是为什么是对的？
     *
     * */
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        int n = r;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (nums[0] <= nums[mid]) {
                if (nums[n] < nums[0]) l = mid + 1;
                else return nums[0];
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
    
    class Solution {
        public int findMin(int[] nums) {
            int low = 0;
            int high = nums.length - 1;
            while (low < high) {
                int pivot = low + (high - low) / 2;
                if (nums[pivot] < nums[high]) {
                    high = pivot;
                } else {
                    low = pivot + 1;
                }
            }
            return nums[low];
        }
    }
    
    // 你岂不是得想得非常清楚？
    public int findMin2(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] < nums[r]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
    
}
